package medium

import "math"

/*
时间复杂度:O(N)
空间复杂度:O(N)

hash+滑动窗口
注意：
	1.这个题的难点在于如何判断窗口中是否包含small中的所有元素
	2.一定要注意这个题求的是最短超串，求最短，一般是在内层循环内部对ans进行更新;求最长一般是在外层for之内和内层for之外的部分对ans进行更新;
	参考: 209. 长度最小的子数组.go
*/

func shortestSeq(big []int, small []int) []int {
	sh := make(map[int]int)
	bh := make(map[int]int)
	for _, v := range small {
		sh[v]++
	}
	sKind, bKind := len(sh), 0
	ansLen := math.MaxInt32
	ans:= make([]int, 0)

	left, right := 0, 0
	for right < len(big) {
		if _, ok := sh[big[right]]; ok {
			bh[big[right]]++
			if bh[big[right]] == sh[big[right]] {
				bKind++
			}
		}
		for bKind == sKind {
			if _, ok := sh[big[left]]; ok {
				if bh[big[left]] > 0 {
					bh[big[left]]--
					if bh[big[left]] == sh[big[left]]-1 {
						bKind--
					}
				}
			}
			if ansLen > right-left+1 {
				ansLen = right - left + 1
				ans = []int{left, right}
			}
			left++
		}
		right++
	}
	return ans
}